package com.yang.Dp.HouseRobber;

/**
 * @Author: yang
 * @Description:
 * @Date: Created in 22:30 2022/9/7
 * @Modified By:
 */

/*
    题目描述
    有n个小朋友，每个小朋友都有自己的座位。恰好每个小朋友都坐错座位的方式有多少种？
    n <= 66
    */

    // 全错位排列问题 网上有公式  dp[i] = (i - 1)(dp[i - 1] * dp[i - 2]
public class SitASeat {
    public static void main(String[] args) {
        int n = 3;
        int[] dp = new int[n + 1];
        // dp[0] dp[1] 没有坐错的可能
        dp[2] = 1;
        for(int i = 3; i <= n; i++){
            dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]);
        }
        System.out.println(dp[n]);
    }
}
